import java.util.Arrays;

/**
 * @ClassName LC31
 * 下一个排列
 * @Author ykx
 * @Date 2024/3/13 17:52
 * @Version 1.0
 */
public class LC31 {
    public void nextPermutation(int[] nums) {
        int length = nums.length;
        for (int i = length - 1; i >= 0; i--) {
            // 若从后往前能遍历到第一个元素，说明整个数组是降序排列，直接升序后返回
            if (i == 0) {
                Arrays.sort(nums);
                return;
            } else {
                // 从右往左遍历到降序序列
                if (nums[i] > nums[i - 1]) {
                    // 对后面的元素排序
                    Arrays.sort(nums, i, length);

                    // 在后面找大于num[i-1]的最小元素，和num[i-1]换位置
                    for (int j = i; j < nums.length; j++) {
                        if (nums[j] > nums[i - 1]) {
                            int temp = nums[j];
                            nums[j] = nums[i - 1];
                            nums[i - 1] = temp;
                            return;
                        }
                    }
                }
            }
        }
    }
}
